package com.cuz.hot100;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;

public class Q43StringMultiplication {

    public static String stringMultiplication1(String num1, String num2) {
        if ("0".equals(num2) || "0".equals(num1)) {
            return "0";
        }
        char[] char1 = num1.toCharArray();
        char[] char2 = num2.toCharArray();
        int[] res = new int[char1.length + char2.length];
        for (int i = char2.length - 1; i >= 0; i--) {
            int[] tempRes = multiply(char1, char2[i] - '0');
            add(res, tempRes, char1.length - i - 1);
        }
        StringBuilder sb = new StringBuilder();
        boolean isNotPreZero = true;
        for (int i = 0; i < res.length; i++) {
            if (isNotPreZero && res[i] == 0) {
                continue;
            }
            isNotPreZero = false;
            sb.append(res[i]);
        }
        return sb.toString();
    }

    private static void add(int[] source, int[] target, int bit) {
        int length = source.length;
        boolean hasCarry = false;
        int count = 1;
        int i = length - bit - 1;
        for (; i > 0 && count < target.length; i--) {
            source[i] += target[target.length - count] + (hasCarry ? 1 : 0);
            if (source[i] >= 10) {
                hasCarry = true;
                source[i] %= 10;
            } else {
                hasCarry = false;
            }
        }
        if (hasCarry) {
            source[i] = 1;
        }
    }

    private static int[] multiply(char[] nums, int i) {
        int[] res = new int[nums.length + 1];
        for (int index = nums.length - 1; index >= 0; index--) {
            int tempRes = i * nums[index] - '0';
            int bit = nums.length - index;

            res[res.length - bit] += tempRes % 10;
            boolean hasCarry = false;
            if (res[res.length - bit] >= 10) {
                res[res.length - bit] %= 10;
                hasCarry = true;
            }
            res[res.length - bit - 1] += tempRes / 10;
            if (hasCarry) {
                res[res.length - bit - 1] += 1;
            }
        }
        return res;
    }

    public static String stringMultiplication(String num1, String num2) {
        if (num2.equals("0") || num1.equals("0")) {
            return "0";
        }
        char[] chars = num2.toCharArray();
        String res = "0";
        for (int i = chars.length - 1; i >= 0; i--) {
            String tempRes = charMultiplyString(num1, chars[i])
                    + zeroGenerate(chars.length - i - 1);
            res = stringAddString(res, tempRes);
        }
        return res;
    }

    private static String charMultiplyString(String num1, char num2) {
        char[] chars = num1.toCharArray();
        String res = "0";
        for (int i = chars.length - 1; i >= 0; i--) {
            String tempRes = charMultiplyChar(chars[i], num2) + zeroGenerate(chars.length - i - 1);
            res = stringAddString(tempRes, res);
        }
        return res;
    }

    private static String zeroGenerate(int n) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            stringBuilder.append(0);
        }
        return stringBuilder.toString();
    }

    private static String charMultiplyChar(char num1, char num2) {
        return String.valueOf((num1 - '0') * (num2 - '0'));
    }

    private static String stringAddString(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int len1 = chars1.length;
        int len2 = chars2.length;
        boolean hasCarry = false;
        LinkedList<Integer> listMemory = new LinkedList<>();
        for (int index = 1; index < len1 + 1 || index < len2 + 1; index++) {
            int num1 = zeroOutBounds(chars1, len1 - index);
            int num2 = zeroOutBounds(chars2, len2 - index);
            int sum = num1 + num2 + (hasCarry ? 1 : 0);
            if (sum >= 10) {
                hasCarry = true;
                sum = sum % 10;
            } else {
                hasCarry = false;
            }
            listMemory.addFirst(sum);
        }
        if (hasCarry) {
            listMemory.addFirst(1);
        }
        StringBuilder res = new StringBuilder();
        for (Integer integer : listMemory) {
            res.append(integer);
        }
        return res.toString();
    }

    private static int zeroOutBounds(char[] chars, int index) {
        if (index < 0 || index >= chars.length) {
            return 0;
        }
        return chars[index] - '0';
    }

    public static void main(String[] args) {
//        int[] ints = {9,9, 9};
//        System.out.println(Arrays.toString(multiply(ints, 9)));
//        int[] ints2 = {9, 0, 0};
//        int[] ints1 = {9, 9};
//        add(ints2, ints1, 0);
//        System.out.println(Arrays.toString(ints2));
//        ints2 = new int[]{0, 9, 0, 0};
//        add(ints2, ints1, 1);
//        System.out.println(Arrays.toString(ints2));
        System.out.println(stringMultiplication1("999191", "10889"));
        System.out.println(BigInteger.valueOf(999191).multiply(BigInteger.valueOf(10889)));
        System.out.println();
    }
}
